package 中等.前缀和与差分;

/**
 * 给你一个由若干 0 和 1 组成的二维网格 grid，请你找出边界全部由 1 组成
 * 的最大 正方形 子网格，并返回该子网格中的元素数量。如果不存在，则返回 0。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/largest-1-bordered-square
 */
public class 最大的以1为边界的正方形_1139 {

    public static void main(String[] args) {

        System.out.println(largest1BorderedSquare(
                new int[][]{{1, 1, 1}, {1, 1, 1}, {1, 1, 1}}));

    }

    /**
     * 预处理+枚举(正方形左上方点和边长)
     */
    public static int largest1BorderedSquare(int[][] grid) {
        int[][] prefixSumRow = new int[grid.length][grid[0].length];
        int[][] prefixSumColumn = new int[grid.length][grid[0].length];

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 0) continue;
                prefixSumRow[i][j] = 1;
                prefixSumColumn[i][j] = 1;
                if (i > 0) {
                    prefixSumRow[i][j] += prefixSumRow[i - 1][j];
                }
                if (j > 0) {
                    prefixSumColumn[i][j] += prefixSumColumn[i][j - 1];
                }
            }
        }
        int ans = 0;

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                int curBorder = 0;
                while (true) {
                    if (i + curBorder >= grid.length || j + curBorder >= grid[0].length) break;

                    if (prefixSumRow[i + curBorder][j] >= curBorder + 1 &&
                            prefixSumRow[i + curBorder][j + curBorder] >= curBorder + 1 &&
                            prefixSumColumn[i][j + curBorder] >= curBorder + 1 &&
                            prefixSumColumn[i + curBorder][j + curBorder] >= curBorder + 1) {
                        ans = Math.max(ans, (curBorder + 1) * (curBorder + 1));
                    }
                    curBorder++;
                }
            }
        }
        return ans;
    }

}
